#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

int ans;

array <int, 20> idx;

void dfs(vector <vector <int> > g, int step) {
    if (step > ans) return;
    for (int i = 0; i < g.size(); i++)
        idx[i] = i;
    do {
        bool flg = 1;
        for (int i = 0; i < g.size(); i++) {
            bool _flg = 0;
            for (auto j : g[i])
                _flg |= (idx[j] == ((idx[i] + 1) % g.size()));
            flg &= _flg;
        }
        if (flg) {
            /* for (int i = 0; i < g.size(); i++) { */
                /* for (auto j : g[i]) */
                    /* cerr << j << " "; */
                /* cerr << endl; */
            /* } */
            ans = step;
            return;
        }
    } while (next_permutation(idx.begin(), idx.begin() + g.size()));
    vector <vector <int> > h;
    for (int i = 0; i < g.size(); i++) {
        for (int j = 0; j < g.size(); j++) {
            if (i == j) continue;
            h.clear();
            for (int k = 0; k < g.size(); k++)
                idx[k] = k - i < k;
            idx[j] = g.size() - 2;
            for (int k = 0; k < g.size(); k++) {
                if (k != i && k != j) {
                    h.push_back(vector <int>());
                    for (auto p : g[k])
                        h.back().push_back((p != i ? idx[p] : idx[j]));
                }
            }
            h.push_back(vector <int>());
            for (auto p : g[j])
                h.back().push_back((p != i ? idx[p] : idx[j]));
            for (auto p : g[i])
                h.back().push_back((p != i ? idx[p] : idx[j]));
            dfs(h, step + 1);
        }
    }
}

void solve() {
    int n = read(), m = read();
    vector <vector <int> > g; g.resize(n, vector <int>());
    ans = 2e9;
    for (int i = 1, x, y; i <= m; i++)
        x = read(), y = read(), g[x].push_back(y);
    dfs(g, 0);
    write(ans), puts("");
}

bool _edmer;
int main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
#ifndef cxqghzj
    freopen("circ.in", "r", stdin);
    freopen("circ.out", "w", stdout);
#endif
    int T = read();
    while (T--) solve();
    return 0;
}
